1. Field of the Invention
The present invention relates to arbitration circuits for arbitrating among bus access requests in data processing systems having a plurality of bus masters connected through a shared bus, and particularly to an arbitration circuit used in a multiprocessor in which a plurality of processors are connected through a shared bus.
2. Description of the Background Art
When a plurality of I/O modules share a common bus, a method called “round robin” is adopted to arbitrate bus access from the I/O modules.
Round robin control assigns the lowest access priority to an I/O module that was granted bus access, so that the I/O modules have equal opportunity for bus access.
As for conventional techniques using the round robin control, Japanese Patent Application Laid-Open No. 10-91577 (1998), columns 3 to 11, FIGS. 1 to 3 (Patent Document 1) discloses a scheme combining priority control and round robin control, where access is allowed in accordance with the importance levels of I/O modules.
Japanese Patent Application Laid-Open No. 4-328665 (1992), pp. 4 to 6, FIGS. 1 to 3 (Patent Document 2) also discloses a combination of priority control and round robin control, where each processor is provided with two kinds of priorities and the highest-priority processor is determined in accordance with combinations of the two kinds of priorities.
Further, Japanese Patent Application Laid-Open No. 1-197865 (1989), pp. 3 to 5, FIGS. 1 to 6 (Patent Document 3) discloses a technique in which, when bus access from a module with a low priority is rejected, the time is measured so as to preferentially grant bus access to that module if that module is not awarded access for a predetermined time period or longer.
Common round robin control schemes accept any requests from I/O modules in order, regardless of the contents of the requests, without distinguishing between important requests for system operation and requests that may be nullified, such as instruction prefetch requests (pre-reads of data). On the other hand, Patent Documents 1 to 3 disclose examples incorporating control schemes that consider priority as well. However, these techniques may fail to provide fair bus access because I/O modules with low priorities may be left without being awarded any opportunity for bus access.